Today, bit-serial processors are in widespread use. For example, bit-serial processors are commonly used to efficiently carry out pixel, or bit-plane, operations in image processing applications. See, for example, U.S. patent application Ser. No. 09/057,482, entitled "Mesh Connected Computer" (filed on Apr. 9, 1998 in the name of Abercrombie), which describes a system for performing image processing operations using arrays of coupled bit-serial processors. As the teachings of the present invention are useful in a system such as that described in the aforementioned patent application, the aforementioned patent application is incorporated herein in its entirety by reference. Those skilled in the art will appreciate, however, that the teachings of the present invention are broadly applicable in bit-serial processors generally, irrespective of the particular form of bit-serial processor in which the invention is employed.
Generally, and for purposes of the discussion that follows, a bit-serial processor is any processor including an arithmetic logic unit configured to operate on single-bit, or few-bit, data and/or control inputs. The arithmetic logic used to construct such a bit-serial processor is typically minimal, and such logic is most often used to access and process only single-bit operands within a given clock cycle. Thus, an individual bit-serial processor typically provides an elemental computing platform. However, when many bit-serial processors are coupled in a strategic fashion, they are quite powerful, and extremely fast, particularly in applications in which a common operation must be performed simultaneously on many single-bit, or few-bit, operands. Such is often the case, for example, in image processing applications, wherein entire pixel-data bit-planes are manipulated in unison. See, for example, the above incorporated patent application.
By definition, then, conventional bit-serial processors require many clock cycles to perform multi-pass operations such as multiplying or dividing two multiple-bit numbers. Whereas a multiple-bit processor can employ considerable arithmetic and control logic to enable multiple-bit computations to occur within a single or very few clock cycles, conventional bit-serial processors expend many clock cycles performing multiple-bit computations in a multiple-pass fashion. Nonetheless, an ability to quickly perform multiple-bit computations is often critical to the overall performance of a bit-serial processing application. Consequently, there is a need for improved methods and apparatus for performing multiple-bit operations using bit-serial processors.